"""
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。
    首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
    然后，再从剩余未排序元素中继续寻找最小（大）元素，
    然后放到已排序序列的末尾。
    以此类推，直到所有元素均排序完毕。
时间复杂度：O(N^2)
"""


def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        idx = i  # 初始化下标
        for j in range(i + 1, n):  # 遍历后面数组
            if arr[idx] > arr[j]:  # 查找后面数组最小
                idx = j  # 将下标更新为更小值的下标
        arr[i], arr[idx] = arr[idx], arr[i]  # 与最小值的下标交换位置


if __name__ == '__main__':
    test_arr = [64, 25, 12, 22, 11]
    selection_sort(test_arr)
    print(test_arr)
